package jianzhioffer;

import java.util.*;

public class PathSum {

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(root, target, res, path);
        return res;
    }

    // 前序遍历+路径搜索
    private void dfs(TreeNode root, int target, List<List<Integer>> res, List<Integer> path) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left==null && root.right==null) {
            // 细节：为什么我要通过构造方法传入path，不能直接res.add(path)
            //      因为直接加入，加入的是引用(指向的堆中数据会变化)，需要克隆一份加入
            res.add(new ArrayList<>(path));
        }
        dfs(root.left, target, res, path);
        dfs(root.right, target, res, path);
        path.remove(path.size()-1);
    }
}
